10541. Полоса

Полоса длины n состоит из черных и белых квадратов единичного размера. Полоса кодируется последовательностью чисел – количеством черных клеток, которые стоят рядом слева направо.

Например, приведенная выше полоса имеет код 2, 3, 2, 8, 1. При этом не учитывается количество белых клеток, которыми разделяются черные клетки. Указанному коду соответствует и такая полоса:

По длине полосы n и ее коду найти количество разных полос, которые этому коду удовлетворяют.

Вход. Первая строка содержит количество тестов t (1 < t < 20). Каждая следующая строка является отдельным тестом и содержит длину полосы n (1 £ n £ 200), длину кода g (0 £ g £ (n + 1) / 2) и сам код (g натуральных чисел).

Выход. Для каждого теста вывести количество полос длины n, которые удовлетворяют заданному коду.

Пример входа

3

4 0

5 2 1 2

4 2 2 2

Пример выхода

1

3

0

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть имеется w белых квадратов и g групп черных квадратов. Поскольку группы черных квадратов не касаются, то должно существовать как минимум g – 1 белых квадратов (если таковых не существует – то ответ 0). При этом w – (g – 1) белых квадратов будут свободными, и их можно расположить в любом месте по отношению к группам черных квадратов. Количество мест, по которым можно расположить свободные белые квадраты, равно (g + 1). Это можно сделать способами. Здесь = – количество способов расположить r одинаковых объектов по n разным местам, где каждое место может содержать произвольное количество объектов. Таким образом

= =

Пример

Рассмотрим второй тест. Существует три полосы длины 5 с кодом 1 2:

Число свободных белых квадратов равно 1, число групп 2. Следовательно количество мест, куда можно поставить 1 свободный белый квадрат, равно 3. Количество вариантов искомой расстановки равно 3, так как свободный квадрат можно поставить на одно из 3 мест.

Воспользуемся формулой. Число белых квадратов w = 2, число групп g = 2. Количество полос равно = = 3.

Реализация алгоритма

Технически задача сводится к вычислению биномиального коэффициента, значение которого не помещается в 64-битный целый тип. Воспользуемся классом BigInteger.

int n, g, w, group[200];

int i, j, tests;

class BigInteger{ . . .};

BigInteger Cnk(int k, int n)

{

BigInteger res(1);

for(int i = 1; i <= k; i++)

res = res * (n - i + 1) / i;

return res;

}

Читаем количество тестов tests. Для каждого теста считываем код в массив group, параллельно суммируя количество черных квадратов. Вычитаем его из n, получим число белых квадратов w. Если количество белых квадратов w меньше g – 1, то полосы с таким кодом не существует. Иначе вычисляем и выводим результат .

scanf("%d",&tests);

for(i = 0; i < tests; i++)

{

scanf("%d %d",&n,&g);

w = 0;

for(j = 0; j < g; j++)

{

scanf("%d",&group[j]);

w += group[j];

}

w = n - w;

if (w < g - 1) printf("0");

else Cnk(w-g+1,w+1).print();

printf("\n");

}

Java реализация

import java.util.*;

import java.math.*;

public class Main

{

static BigInteger Cnk(int n, int k)

{

BigInteger res = BigInteger.ONE;

for (int i = 0; i < k; i++)

res = res.multiply(BigInteger.valueOf(n-i)).

divide(BigInteger.valueOf(i+1));

return res;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

for(int i = 0; i < tests; i++)

{

int n = con.nextInt();

int g = con.nextInt();

int w = 0;

int[] group = new int[201];

for(int j = 0; j < g; j++)

{

group[j] = con.nextInt();

w += group[j];

}

w = n - w;

if (w < g - 1) System.out.println("0");

else System.out.println(Cnk(w+1,w-g+1));

}

con.close();

}

}